/*
 * @lc app=leetcode.cn id=432 lang=typescript
 *
 * [432] 全 O(1) 的数据结构
 */

// @lc code=start
class LinkNode {
  keys: Set<string>;
  next: LinkNode | null;
  prev: LinkNode | null;
  constructor(public key?: string, public count?: number) {
    this.keys = new Set<string>();
    if (key !== void 0) this.keys.add(key);
    if (count !== void 0) this.count = count;
  }

  insert(node: LinkNode) {
    node.next = this.next;
    node.prev = this;
    node.prev.next = node;
    node.next.prev = node;
  }

  remove() {
    this.prev.next = this.next;
    this.next.prev = this.prev;
  }
}

class AllOne {
  root: LinkNode;
  map: Map<string, LinkNode>;
  constructor() {
    // 使用双向链表存储数据,按照升序排列
    this.root = new LinkNode();
    this.root.next = this.root;
    this.root.prev = this.root;
    // 使用map存储结点
    this.map = new Map();
  }

  inc(key: string): void {
    if (this.map.has(key)) {
      const curr = this.map.get(key);
      const next = curr.next;
      if (curr.next === this.root || next.count > curr.count + 1) {
        // 下一个count比当前的大，或者只有一个结点。直接在当前结点后面插入
        const node = new LinkNode(key, curr.count + 1);
        curr.insert(node);
        this.map.set(key, node);
      } else {
        //  下一个结点的count刚好相等，直接更新下一个结点的值
        next.keys.add(key);
        this.map.set(key, next);
      }
      curr.keys.delete(key);
      if (curr.keys.size === 0) {
        curr.remove();
      }
    } else {
      if (this.root.next === this.root || this.root.next.count > 1) {
        const node = new LinkNode(key, 1);
        this.root.insert(node);
        this.map.set(key, node);
      } else {
        this.root.next.keys.add(key);
        this.map.set(key, this.root.next);
      }
    }
  }

  dec(key: string): void {
    const curr = this.map.get(key);
    if (curr.count === 1) {
      this.map.delete(key);
    } else {
      const prev = curr.prev;
      if (prev === this.root || prev.count < curr.count - 1) {
        const node = new LinkNode(key, curr.count - 1);
        prev.insert(node);
        this.map.set(key, node);
      } else {
        prev.keys.add(key);
        this.map.set(key, prev);
      }
    }
    curr.keys.delete(key);
    if (curr.keys.size === 0) {
      curr.remove();
    }
  }

  getMaxKey(): string {
    if (this.root.prev === this.root) return '';
    for (const maxKey of this.root.prev.keys) {
      return maxKey;
    }
  }

  getMinKey(): string {
    if (this.root.next === this.root) return '';
    for (const minKey of this.root.next.keys) {
      return minKey;
    }
  }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * var obj = new AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * var param_3 = obj.getMaxKey()
 * var param_4 = obj.getMinKey()
 */
// @lc code=end
